package exp5;

import java.util.LinkedList;
import java.util.List;

public class SeparateChainingHashTable<AnyType> {
    public SeparateChainingHashTable() {
        this(DEFAULT_TABLE_SIZE);
    }

    public SeparateChainingHashTable(int size) {
        theLists = new LinkedList[nextPrime(size)];//确定链表长度
        for (int i = 0; i < theLists.length; i++) {
            theLists[i] = new LinkedList<>();
        }
    }

    //插入
    public void insert(AnyType x) {
        int position = myhash(x);
        List<AnyType> whichList = theLists[position];
        if (false == whichList.contains(x)) {
            whichList.add(x);
        }
    }

    //删除
    public void remove(AnyType x) {
        List<AnyType> whichList = theLists[myhash(x)];
        if (whichList.contains(x)) {//判断hash表中是否有要删除的元素
            whichList.remove(x);
            currentSize--;
        }
    }

    //找位置
    public boolean contains(AnyType x) {
        int position = myhash(x);
        List<AnyType> whichList = theLists[position];
        return whichList.contains(x);//继续判断这个位置是否有该值
    }

    public void makeEmpty() {
        for (int i = 0; i < theLists.length; i++) {
            theLists[i].clear();
        }
        currentSize = 0;
    }

    //h(x) =x%11
    private int myhash(AnyType x) {//求hash值
        int hashVal = x.hashCode();

        hashVal %= 11;
        if (hashVal < 0)//防止余数为负数
        {
            hashVal += 11;
        }
        return hashVal;
    }

    private static final int DEFAULT_TABLE_SIZE = 11;
    public List<AnyType>[] theLists;
    private int currentSize;

    private static int nextPrime(int n) {
        if (n % 2 == 0) {
            n++;
        }
        for (; !isPrime(n); n += 2) {
            ;
        }
        return n;
    }

    private static boolean isPrime(int n)//判断是否为素数
    {
        if (n == 2 || n == 3) {
            return true;
        }

        if (n == 1 || n % 2 == 0) {
            return false;
        }

        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        SeparateChainingHashTable<Integer> H = new SeparateChainingHashTable<>();
        H.insert(4371);
        H.insert(1223);
        H.insert(6173);
        H.insert(4199);
        H.insert(4344);
        H.insert(9679);
        H.insert(1989);
        for (int i = 0; i < H.theLists.length; i++) {
            System.out.println("{" + i + ":" + H.theLists[i] + "}");
        }
    }
}